//给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 
//
// 你需要返回给定数组中的重要翻转对的数量。 
//
// 示例 1: 
//
// 
//输入: [1,3,2,3,1]
//输出: 2
// 
//
// 示例 2: 
//
// 
//输入: [2,4,3,5,1]
//输出: 3
// 
//
// 注意: 
//
// 
// 给定数组的长度不会超过50000。 
// 输入数组中的所有数字都在32位整数的表示范围内。 
// 
// Related Topics 排序 树状数组 线段树 二分查找 分治算法


package leetcode.d_300_plus;

import java.util.Arrays;

//Java：翻转对
public class P493ReversePairs{
    public static void main(String[] args) {
        Solution solution = new P493ReversePairs().new Solution();
        int[] array = {2,4,3,5,1};
        System.out.println(solution.reversePairs(array));
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length-1);
    }

    public int mergeSort(int[] nums, int left, int right){
        if (left >= right){
            return 0;
        }
        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid) + mergeSort(nums, mid+1, right);
        for (int i = left, j = mid+1; i <= mid; i++) {
            while (j <= right && nums[i]/2.0 > nums[j]){
                j++;
            }
            count += j - (mid + 1);
        }
        Arrays.sort(nums, left, right+1);
        return count;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}